package org.algorithm.biubiu.wheel_1.数组.三月.第三周;

import java.util.Arrays;

/**
 * @version 1.0
 * @date 2022/03/16 9:08 PM
 * @description:
 *
 *
 * url: https://leetcode-cn.com/problems/frequency-of-the-most-frequent-element/
 *
 * TODO need check
 */
public class 最高频元素的频数 {

    public static void main(String[] args) {
        int[] nums = {1,2,4,6};
        System.out.println(maxFrequency(nums, 5));
    }

    /**
     1,2,4,6
     sum += (nums[right]-nums[right-1])*(right-left);
     第一次循环  num  1,2,4 ,6
     第一次循环  num  2,2,4 ,6
     第三次循环  num  4,4,4 ,6
     每次循环 已经将差值 添加进到sum了。

     sum-= nums[right]-nums[left];
     1236  left = 0 right = 3 这个窗口已经不满足了。 需要left右移。
     这个时候 需要讲  num[right]-num[left] 中间的差值 空余出来
     */

    public static int maxFrequency(int[] nums, int k){

        Arrays.sort(nums);
        int left = 0;
        int sum = 0;
        int res = 1;
        for(int right=1;right<nums.length; right++ ){
            // why  ->   1，2，4，6】
            sum += (nums[right]-nums[right-1])*(right-left);
            if(sum>k){
                sum-= nums[right]-nums[left];
                left++;
            }
            res = Math.max(right-left+1,res);
        }
        return res;
    }
}
